<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

    <script>
        class Node { 
            constructor(key) {
                this.key = key;
                this.right = null;
                this.left = null;
            }
        }
        class BinarySearchTree {
            constructor() {
                this.root = null;
            }
            //插入insert
            insert(key) {
                const newNode = new Node(key);
                if (this.root === null) {
                    this.root = newNode;
                } else {
                    this.insertNode(this.root, newNode)
                }
            }
            //insertNode二叉搜索树插入节点的操作
            insertNode(node, newNode) {
                if (newNode.key > node.key) {
                    if (node.right === null) {
                        node.right = newNode
                    } else {
                        this.insertNode(node.right, newNode);
                    }
                } else {
                    if (node.left === null) {
                        node.left = newNode
                    } else {
                        this.insertNode(node.left, newNode);
                    }
                }
            }
            //preOrderTraverse: 先序遍历
            preOrderTraverse() {
                this.preOrderTraverseNode(this.root);
            }
            preOrderTraverseNode(node) {
                if (node === null) return;

                console.log(node.key);  //直接访问
                this.preOrderTraverseNode(node.left);
                this.preOrderTraverseNode(node.right);
            }
            //inOrderTraverse 中序遍历
            inOrderTraverse() {
                this.inOrderTraverseNode(this.root)
            }
            inOrderTraverseNode(node) {
                if (node === null) return;

                this.inOrderTraverseNode(node.left);
                console.log(node.key);
                this.inOrderTraverseNode(node.right);
            }
            //postOrderTraverse 后序遍历
            postOrderTraverse() {
                this.postOrderTraverseNode(this.root)
            }
            postOrderTraverseNode(node) {
                if (node === null) return;

                this.postOrderTraverseNode(node.left);
                this.postOrderTraverseNode(node.right);
                console.log(node.key);
            }
            //min 返回最小值
            min() {
                if (this.root === null) return null;
                let node = this.root;

                while (node.left !== null) {
                    node = node.left;
                }
                return node.key;
            }
            //max 返回最大值
            max() {
                if (this.root === null) return null;
                let node = this.root;

                while (node.right !== null) {
                    node = node.right
                }
                return node.key;
            }
            //search(key) 在中查找一个值，如果节点存在返回true 如果节点不存在返回false
            search(key) {
                return this.searchNode(this.root, key)
            }
            searchNode(node, key) {
                //1.判断node有没有值
                if (node === null) return false;
                //2.判断搜索的key和节点值的关系
                if (key < node.key) {
                    return this.searchNode(node.left, key);
                } else if (key > node.key) {
                    return this.searchNode(node.right, key);
                } else return true;
            }

            search2(key) {
                let node = this.root;

                while (node !== null) {
                    if (key > node.key) {
                        node = node.right;
                    } else if (key < node.key) {
                        node = node.left;
                    } else return true;
                }
                return false;
            }

            //remove(key)   //删除指定节点
            remove(key) {
                //1.找到要删除的节点
                let current = this.root;
                let parent = null;
                let isLeftChild = true;
                //2.开始查找要删除的节点
                while (current.key !== key) {
                    parent = current;
                    if (key > current.key) {
                        isLeftChild = false;
                        current = current.right;
                    } else {
                        isLeftChild = true;
                        current = current.left;
                    }
                    if (current === null) return false;
                }
                //3.找到我们的节点current和parent
                //情况一：删除的子节点是叶子结点(没有子结点)
                if (current.left === null && current.right === null) {
                    if (current === this.root) {
                        this.root = null;
                    } else if (isLeftChild) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }
                //情况二：删除的子结点只有一个分支结点
                else if (current.right === null) {//只有左子节点
                    if (current === this.root) {
                        this.root = current.left;
                    } else if (isLeftChild) {
                        parent.left = current.left;
                    } else {
                        parent.right = current.left;
                    }
                } else if (current.left === null) {//只有右子节点
                    if (current === this.root) {
                        this.root = current.right;
                    } else if (isLeftChild) {
                        parent.left = current.right;
                    } else {
                        parent.right = current.right;
                    }
                } else {
                    //1.获取后继节点
                    let successor = this.getSuccessor(current);//获取到要删除的节点
                    //2.判断是否是根节点
                    if (current === this.root) {
                        this.root = successor;
                    } else if (isLeftChild) {
                        parent.left = successor;
                    } else {
                        parent.right = successor;
                    }
                    successor.left = current.left;
                }


                return true;
            }

            //获取后继  实现删除
            getSuccessor(delNode) {
                //1.定义变量，来存储临时的节点
                let successerParent = delNode;
                let successer = delNode;
                let current = delNode.right;
                //2.寻找节点
                while (current !== null) {
                    successerParent = successer;
                    successer = current;
                    current = current.left;
                }
                //3.如果后继节点不是删除节点的右节点
                if (successer != delNode.right) {
                    successerParent.left = successer.right;
                    successer.right = delNode.right;
                }
                return successer;
            }
        }

        let bst = new BinarySearchTree();
        bst.insert(11);
        bst.insert(7);
        bst.insert(15);
        bst.insert(5);
        bst.insert(3);
        bst.insert(9);
        bst.insert(6);
        bst.insert(13);
        bst.insert(12);
        bst.insert(8);
        bst.insert(10);
        bst.insert(14);
        bst.insert(20);
        bst.insert(18);
        bst.insert(25);


        // console.log(bst);
        // bst.preOrderTraverse();
        // console.log("______");
        // bst.inOrderTraverse()
        // console.log("______");

        // bst.postOrderTraverse();
        console.log(bst.min());
        console.log(bst.max());
        // console.log(bst.search(2));
        // console.log(bst.search(25));
        // console.log(bst.search2(25));
        // console.log(bst.search2(2));
        bst.remove(9);
        console.log(bst);
    </script>
</body>

</html>